package utils;

import data.Cities;
import data.Tree;

public class MinimumSpanningTree extends Tree {
    double Cost;
    
    public MinimumSpanningTree(Cities c) {        
        setN(c.getN());        
        double[] label = new double[c.getN() + 1];
        boolean[] visited = new boolean[c.getN() + 1];
        for (int i = 1; i <= getN(); i++) {
            label[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }
        label[1] = 0;
        for (int i = 1; i < getN(); i++) {
            double min = Integer.MAX_VALUE;
            int choose = 0;
            for (int j = 1; j <= getN(); j++)
                if (min > label[j] && !visited[j]) {
                    choose = j;
                    min = label[j];
                }
            if (min == Integer.MAX_VALUE) {
                System.out.println("Can not found MST !!!");
                System.exit(-1);
            }
            visited[choose] = true;
            for (int j = 1; j <= getN(); j++)
                if (!visited[j] && label[j] > c.distance(choose, j)) {
                    setDad(j, choose);
                    label[j] = c.distance(choose, j);
                }                                    
        }
        for (int i = 1; i <= getN(); i++)
            if (getDad(i) != 0)
                Cost += c.distance(i, getDad(i));
        System.out.println("complete MST !!!");
    }
    
    public void displayTree() {
        System.out.println("Tree Cost: " + Cost);
        for (int i = 1; i <= getN(); i++)
            if (getDad(i) != 0)
                System.out.println(i + " " + getDad(i));
    }
}
